One of the most popularly used nonvolatile semiconductor memory chips is a flash memory of the NAND type (referred to as NAND flash memory). In a NAND flash memory, the smallest unit of recording is a page, and writing is performed in units of a page. It is possible to write data into a page, only after the data previously stored in the page has been erased. It is not possible to erase the data in units of a page. The data is erased in units (called “blocks”) each of which is made up of a predetermined number (2 or more) of pages. In the case where the relationship between an address (hereinafter, a “logical address”) that is specified when a host, which is an apparatus superordinate to a semiconductor memory chip, requests writing of data and a page (hereinafter, a “physical address”) into which the data is written within the NAND flash memory is a fixed relationship, every time the host requests writing of data, the data in a block needs to be erased so that the new data can be written into the erased block. In this situation, the other pages (in the same block) on which the writing was not performed are also erased at the same time. To avoid this situation, it is possible to use a method by which the data stored in the pages to be erased is temporarily moved to another memory such as a Dynamic Random Access Memory (DRAM) so that, after the block has been erased, the data requested to be written and the data that has been moved to the other memory are written together into the block.
As explained above, in the case where the relationship between logical addresses and physical addresses is fixed, if the number of times writing processes have been performed is not well balanced among different logical addresses, the number of times writing process have been performed is not be well balanced among different physical addresses, either. Thus, there is a possibility that writing processes may be performed in a concentrated manner in a region with certain physical addresses. NAND flash memories have a characteristic where the element wears out when writing processes have been performed thereon a large number of times. Thus, there is a demand that the number of times writing processes are performed should be as uniform as possible throughout the entirety of the storage region so that the life span of the system can be kept long. To arrange the number of times writing processes are performed to be as uniform as possible throughout the entirety of the storage region, it is necessary to manage the number of times writing processes have been performed in each of sectional regions and to manage the relationship between the logical addresses and the physical addresses in such a manner that writing processes will be performed on some regions on which writing processes have been performed a smaller number of times.
To read the data that has been written by using the method described above in response to a request from the host, it is necessary to determine the storing position (i.e., the physical address) in which the data corresponding to the logical address specified by the host is actually stored within a NAND flash memory. For this purpose, it is necessary to prepare a translation table showing the association between the logical address and the physical address. To be efficient, the units that are used for indicating the association between logical addresses and physical addresses should preferably match the page size of the NAND flash memory; however, the page size may be, for example, 4 kilobytes and is relatively small. For example, in the case where a logical address space of 256 gigabytes is divided into sections of 4 kilobytes each, the translation table needs to have 64 mega entries. On an assumption that each of the entries in the translation table is 4 bytes in size, the translation table will require a capacity of 256 megabytes. It means that the size of the translation table is very large (see, for example, “A Buffer Management Scheme for Improving Random Writes in Flash Storage”, http://www.usenix.org/events/fast08/tech/full_papers/kim/kim_html/).
Generally speaking, a Dynamic Random Access Memory (DRAM) or a Static Random Access Memory (SRAM), each of which has a high level of random accessibility, can be used for translation tables. In the case where the size of a translation table is large, a large part of the capacity of such a volatile memory is required. There is a possibility that making the capacity of a memory larger may lead to a cost-related problem. In addition, in the case where the entirety of the translation table is held in the NAND flash memory itself, every time the translation table is updated, a writing process is performed on the NAND flash memory. As a result, the number of times writing processes are performed on the NAND flash memory increases, and there is a possibility that reliability of the semiconductor memory system may become lower.